#include "main/utils.h"
#include "lib/list.h"
using namespace std;

class Solution {
  public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
      if (!list1)
        return list2;
      if (!list2)
        return list1;
      auto listA = list1;
      auto listB = list2;
      ListNode* new_head;
      if (listA->value < listB->value) {
        new_head = listA;
        listA = listA->next;
      } else {
        new_head = listB;
        listB = listB->next;
      }
      auto new_node = new_head;
      while (listA && listB) {
        if (listA->value < listB->value) {
          new_node->next = listA;
          listA = listA->next;
          new_node = new_node->next;
        } else {
          new_node->next = listB;
          listB = listB->next;
          new_node = new_node->next;
        }
      }
      if (!listA) {
        new_node->next = listB;
      }
      if (!listB) {
        new_node->next = listA;
      }
      return new_head; 
    }

    ListNode* mergeTwoLists1(ListNode* list1, ListNode* list2) {
      if (!list1) {
        return list2;
      }
      if (!list2) {
        return list1;
      }
      if (list1->value < list2->value) {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
      } else {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
      }
    }
};

int main() {
  vector<int> node_vals_a = {1, 2, 4};
  vector<int> node_vals_b = {1, 3, 4};
  ListNode* pheada = CreateList(node_vals_a);
  ListNode* pheadb = CreateList(node_vals_b);
  Solution su;
  auto output = su.mergeTwoLists(pheada, pheadb);
  PrintList(output);

  ListNode* pheada1 = CreateList(node_vals_a);
  ListNode* pheadb1 = CreateList(node_vals_b);
  auto output1 = su.mergeTwoLists1(pheada1, pheadb1);
  PrintList(output1);

  return 0;
}
